#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define SIZE 15

typedef int ElementType;

typedef struct STable
{
    ElementType *elem;
    int len;
} STable;

int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

void InitSTable(STable &table, int len)
{
    table.elem = (ElementType *)malloc(sizeof(ElementType) * len);
    table.len = len;
    srand(time(NULL));
    for (int i = 0; i < len; i++)
    {
        table.elem[i] = rand() % 100;
    }
    qsort(table.elem, table.len, sizeof(int), compare);
}

void PrintSTable(STable table)
{
    for (int i = 0; i < table.len; i++)
    {
        printf("%3d", table.elem[i]);
    }
    printf("\n");
}

int BinarySearch(ElementType elem[], int len, ElementType e)
{
    int left = 0, right = len - 1, mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (elem[mid] == e)
        {
            return mid;
        }
        else if (elem[mid] > e)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;
}

int hash[SIZE] = {0};

void insert(ElementType elem)
{
    int index = elem % SIZE;
    while (hash[index])
    {
        index = (index + 1) % SIZE;
    }
    hash[index] = elem;
}

int hashSearch(ElementType target)
{
    int index = target % SIZE;
    while (hash[index] && hash[index] != target)
    {
        index = (index + 1) % SIZE;
    }
    return hash[index] == target ? index : -1;
}

int main()
{
    STable table;
    InitSTable(table, SIZE);
    PrintSTable(table);
    int targe;
    printf("请输入查找数：");
    scanf("%d", &targe);
    int index = BinarySearch(table.elem, table.len, targe);
    printf("num:%d index is %d", targe, index);
}